package bit_pratice.day3;

/**
 * @author 美女
 * @date 2022/05/04 13:08
 **/
//投票选候选人
public class Num2_3 {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null||array.length==0){
            return 0;
        }
        int target=array[0];
        int times=1;
        for(int i=1;i<array.length;i++){
            //当times=0时说明已经抵消完了，没必要让当前target再和后面数据比较了，将当前arr[i]这个数换给target
            if(times==0){
                target=array[i];
                times=1;
            }
            if(target==array[i]){
                times++;
            }else{
                times--;
            }
        }
        //已经找出候选人target，现在重新统计该候选人的票数
        times=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==target){
                times++;
            }
        }
        //票数统计完毕，看是否超过一半，超过一半才能返回target
        return times>array.length/2?target:0;

    }
}
